package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/7 15:31
 * @DESCRIPTION
 */
// 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
// 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，
// 所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
// 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
// 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
public class 重新安排行程 {
    //看代码随想录中的代码 模仿写出
    //能够理解该题
    //该题难点在于对题目的理解
    //还有需要对字符串进行排序
    //以及 这个回溯算法是有返回值的 为什么会有返回值 其根本原因就是需不需要遍历完整个抽象树来决定的
    private LinkedList<String> res;
    private LinkedList<String> path = new LinkedList<>();
    public List<String> method1(List<List<String>> tickets) {
        //根据字母进行排序
        //这里对stream API还是不是太了解需要加强
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
        //必须从JFK机场起飞
        path.add("JFK");
        //标记 机票是否使用过
        boolean[] used = new boolean[tickets.size()];
        recursion((ArrayList) tickets, used);
        return res;
    }
    //采用boolean返回值 因为不需要遍历整个树 只需要一条满足条件的边即可,因此找到了就可以直接返回，不用继续遍历下去了
    private boolean recursion( ArrayList<List<String>> tickets, boolean[] used) {
        if(path.size()-1>=tickets.size()){
            res=new LinkedList<>(path);
            return true;
        }
        for (int i = 0; i < tickets.size(); i++) {
            //能够加入的机票要满足以下条件
            //1.没被使用过
            //2.出发地是path的最后一个地点
            if(used[i]||!tickets.get(i).get(0).equals(path.peekLast())
                    //这里剪枝  和 全排列中的剪枝 思路一样
                    ||i > 0 && tickets.get(i).get(0).equals(tickets.get(i - 1).get(0))
                    && tickets.get(i).get(1).equals(tickets.get(i - 1).get(1))
                    && !used[i - 1]){
                continue;
            }
            path.add(tickets.get(i).get(1));
            used[i]=true;
            if(recursion(tickets,used)){
                return true;
            }
            used[i]=false;
            path.removeLast();
        }
        return false;
    }
}
